The present invention relates to data compression, and more particularly to distributing video buffer rate control over a parallel compression architecture for a video compression system.
In a conventional frame-based compression encoder algorithm, as shown in FIG. 1, video to be compressed is input in viewing order to a preprocessor, which combines the interlaced fields into frames and reorders the frames for compression based upon the particular compression algorithm, as shown in FIG. 2. The frames in processing order are input to a motion detector which generates motion vectors for each macroblock of a current frame being processed, the motion vectors being provided to an output multiplexer as well as to a predictor module. A predicted frame from the predictor module is compared with the current frame, and the differences are transform coded, typically by a discrete cosine transform module. The resulting transform coefficients are then quantized and variable length encoded before being input to the output multiplexer. The output of the multiplexer includes the coded quantized transform coefficients and associated motion vectors for each macroblock of the current frame.
The output of the quantizer is input to an inverse quantizer and then to an inverse transform coder before being added to the predicted frame to reproduce the current frame for storage in the predictor. The predictor then applies the motion vectors for the next frame to the stored current frame to produce the predicted frame for the next frame. For constant rate applications, i.e., where the number of bits at the output is held to a constant rate, a rate controller as described below is used to change the quantization levels for the quantizer on a frame by frame and macroblock by macroblock basis.
It is common in video compression systems as described above, such as MPEG1 and MPEG2, to use the rate controller to constrain the number of bits needed to represent a compressed image by changing the quality of the compressed image, i.e., a quantizer scale factor. It is often typical for the rate controller to observe R(n-1), the number of bits consumed by the video sequence prior to macroblock n, as provided at the output of the variable length encoder, and then to select the quantizer scale factor Q(n) for the n-th macroblock. Q(n) is used to scale the discrete cosine transform (DCT) coefficients in macroblock n so that when the coefficients are coded and put into an output buffer, the value of R(n) is still reasonably close to its pre-allocated target. Examples of this prior art are described in the paper "Scene Adaptive Coder" by Chen and Pratt in IEEE Trans. Communications, March 1984, and also in the MPEG2 Test Model 3 (Draft) by the Test Model Editing Committee, International Organization for Standardization ISO/IEC/JTC1/SC22/WG11, December 1992. The latter document, for example, checks the buffer fullness status B(n-1) after the previous block and then computes the quality factor Q(n) through the linear relation EQU Q(n)=K.sub.R * B(n-1),
where K.sub.R is a constant that depends on the targeted average bit rate R. This Q(n) may be further scaled based on the visual complexity of the macroblock being coded, as described in U.S. Pat. No. 5,686,964, entitled "Bit Rate Control Mechanism for Digital Image and Video Data Compression."
Additionally one of the requirements in MPEG for generating a correctly coded bit stream is that a Video Buffering Verifier (VBV) is not violated. The VBV is a hypothetical decoder, described in ISO/IEC 13818-2 Annex C, that is conceptually connected to the output of an MPEG encoder. The VBV has an input buffer, known as the VBV buffer, of size B.sub.max bits. The target rate R(n) may have to be adjusted so as not to overflow or underflow the VBV buffer. The occupancy of the VBV buffer for a constant bit-rate operation of MPEG is shown in FIG. 3 where the VBV buffer occupancy B is updated recursively as follows: If Ba(n-1) is the buffer occupancy right after decoding picture (n-1), the buffer occupancy just before decoding picture n,Bb(n), is given by EQU Bb(n)=Ba(n-1)+R,
where R is average bits per picture; and the occupancy Ba(n) just after decoding picture n is given by EQU Ba(n)=Bb(n)-R(n),
where R(n) is the bits actually used for picture n. The relationship between the number of bits per picture R(n) and quality factor Q(n) described above may be used by an MPEG video encoder to:
(1) maintain the constraints imposed by the VBV; PA1 (2) keep the VBV buffer occupancy operating point centered; PA1 (3) enable VBV buffer occupancy terminal conditions to be achieved; and PA1 (4) predict and avoid any potential VBV overflow and underflow condition.
The overall rate control mechanism with VBV buffer consideration is shown in FIG. 4.
In a parallel implementation of a compression encoder, where as shown in FIG. 5 a master controller is coupled to a bus together with a video source, a storage medium and a plurality of client processors, the above techniques suffer from an overly centralized control. This leads to delays due to the overhead of passing messages between the parallel client processors, thus slowing down the system to cancel out the potential speedups due to the use of parallel processors. In particular suppose the compression encoder splits each picture between k parallel processors with each processor compressing non-overlapping slices of the picture as shown in FIG. 6, where a slice is defined to be any horizontally contiguous row of macroblocks no more than one macroblock in height. Each slice may be compressed independently of the other slices with the resulting bit streams being concatenated, i.e., the slices are independent except for the rate control calculations and VBV buffer checks described above. Maintaining the rate controller as above requires that the k processors exchange messages with a central rate controller process before and after encoding each macroblock. In most parallel processing architectures this amount of message passing is too large an overhead on the system and unduly slows down the computations.
What is desired is a compression architecture that distributes video buffer rate control over parallel processors without imposing too large an overhead on the system.